package sword2offer;

/**
 * <p>
 *  I. 在排序数组中查找数字 I
 * </p>
 * 统计一个数字在排序数组中出现的次数。
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * @author LovelyBigDuck
 * @date 2022/3/16 21:15
 */

/**
 * 方案一：遍历存入HashMap，但是遍历太长
 * 方案二：二分查找
 *      1、定义左右边界
 *      2、计算中点位置：[i+j]/2向下取整
 *      2、当左右边界内没有元素时跳出
 */
public class S_53 {
    class Solution {
        // 此种二分法极端条件下会退化
        public int search(int[] nums, int target) {
            int low = 0;
            int high = nums.length - 1;

            while (low <= high) {
                int mid = low + (high - low) / 2;
                if(nums[mid] < target) {
                    low = mid + 1;
                } else if (nums[mid] > target) {
                    high = mid - 1;
                } else {
                    if (nums[low] == nums[high]) {
                        return high - low + 1;
                    }
                    if (nums[low] < target) {
                        low++;
                    }
                    if (nums[high] > target) {
                        high--;
                    }
                }
            }
            return 0;
        }
        // 对于已经排好序的数据首先考虑二分查找
        public int search1(int[] nums, int target) {
            if(nums == null || nums.length == 0) return 0;
            //右边不能越界
            int result = 0, left = 0, right = nums.length-1, mid = 0;
            //小于最小区间是2，等于最小区间为1，保证遍历所有子区间
            //right = mid-1;left = mid+1;保证最小区间从2到1，循环可以结束
            while(left <= right) {
                //向下取整确保不越界
                mid = (left+right)/2;
                if(target == nums[mid]) {
                    int l = mid, r = mid+1;
                    while(l >= 0) {
                        if(nums[l--] == target) result++;
                    }
                    while(r < nums.length) {
                        if(nums[r++] == target) result++;
                    }
                    //跳出循环
                    return result;
                }else if(target < nums[mid]){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
            return result;
        }

        // 先找到首次出现的位置，然后向前或者向后统计
        public int search2(int[] nums, int t) {
            int n = nums.length;
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (nums[mid] > t) r = mid-1;
                else l = mid + 1;
            }
            int ans = 0;
            while (l < n && nums[l] == t) {
                l++;
                ans++;
            }
            return ans;
        }
    }
}
